package com.leetcode.array_matrix;

import java.util.*;

/**
 * @author Dennis Li
 * @date 2020/7/29 19:46
 */
public class FindShortestSubArray_697 {

    public int findShortestSubArray(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        // 最大次数对应的num
        Set<Integer> set = new HashSet<>();
        // num对应的序号。用数组记录，int[0]代表最小坐标，int[1]代表最大坐标
        Map<Integer, int[]> map2 = new HashMap<>();
        int max = 0;
        for (int num : nums) {
            // 更新最大的次数
            int times = map.getOrDefault(num, 0) + 1;
            if (times > max) {
                // 出现了更大次数。清空set，并添加num
                set.clear();
                set.add(num);
                max = times;
            } else if (times == max)
                // 次数一致，出现了新的num
                set.add(num);
            map.put(num, times);
        }
        // 如果全部只出现了一次，那么直接返回1
        if (max == 1) return 1;
        for (int i = 0; i < nums.length; i++) {
            // 检查当前的num值是否在集合中
            if (set.contains(nums[i])) {
                // map2没有，那么赋初值
                if (!map2.containsKey(nums[i])) {
                    map2.put(nums[i], new int[]{i, i});
                } else {
                    // 更改最大最小的坐标
                    int[] ints = map2.get(nums[i]);
                    map2.get(nums[i])[0] = Math.min(ints[0], i);
                    map2.get(nums[i])[1] = Math.max(ints[1], i);
                }
            }
        }
        int minLen = Integer.MAX_VALUE;
        for (int[] value : map2.values()) {
            minLen = Math.min(minLen, value[1] - value[0]);
        }
        // 最后结果要记得加一，比如序号[1,2,2,3]。最小序号是1，最大序号是2，相减得1，但是长度为2
        return minLen + 1;
    }

}
